package com.cet.algorithm.二叉树.修剪二叉搜索树;

/**
 * @program: cet-practice
 * @description: 修剪二叉树
 * @author: 陈恩涛
 * @create: 2023-04-06 21:29
 **/
public class LC669 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(0, null, new TreeNode(2, new TreeNode(1), null)), new TreeNode(4));
        System.out.println(trimBST(root, 1, 3));
    }

    static TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

        if (root.val > high) {
            // 找到左子树中满足范围的节点
            return trimBST(root.left, low, high);
        }
        if (root.val < low) {
            // 找到右子树中满足范围的节点
            return trimBST(root.right, low, high);
        }

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
